<?php


namespace XiaoGuai\DataStructure\BinaryTree\BinaryTree;

use XiaoGuai\DataStructure\BinaryTree\BinaryTree\BinaryTreeNode as Node;
use SplStack;
use SplQueue;

/**
 * 二叉树的基本操作
 * Class BinaryTree
 * @package XiaoGuai\DataStructure\BinaryTree\BinaryTree
 */
class BinaryTree
{
    /**
     * @var null|Node 树的根结点
     */
    protected $root = null;

    public function __construct()
    {

    }

    // 二叉树建立
    public function create(array $orders = [])
    {
        $this->createBinaryTreePreOrder($tree, $orders);
        $this->root = $tree;
    }

    /**
     * 按照完全二叉树的遍历顺序
     * @param $tree
     * @param array $orders ["A", "B", "C", null, "F"]
     */
    protected function createBinaryTreePreOrder($orders = [])
    {
        if (empty($orders)) {
            return null;
        }

        $data = array_shift($orders);
        if (is_null($data)) {
            return null; // null 表示子树为空
        }

        // 建立根结点
        $node = new Node();
        $node->data = $data;

        // 建立左子树
        $node->left = $this->createBinaryTreePreOrder(array_shift($orders));
        // 建立右子树
        $node->right = $this->createBinaryTreePreOrder(array_shift($orders));

        return $node;
    }

    /**
     * 按照完全二叉树的遍历顺序
     * @param array $orders ["A", "B", "C", null, "F"]
     */
    protected function createBinaryTreeInOrder($orders = [])
    {
        if (empty($orders)) {
            return null;
        }
        $node = new Node();

        // 建立左子树
        $node->left = $this->createBinaryTreeInOrder(array_shift($orders));

        // 建立根结点
        $data = array_shift($orders);
        if (is_null($data)) {
            return null; // null 表示子树为空
        }
        $node->data = $data;

        // 建立右子树
        $node->right = $this->createBinaryTreeInOrder(array_shift($orders));

        return $node;
    }

    /**
     * 按照完全二叉树的遍历顺序
     * @param array $orders ["A", "B", "C", null, "F"]
     */
    protected function createBinaryTreePostOrder($orders = [])
    {
        if (empty($orders) || $orders[0] === null) {
            return null;
        }
        $node = new Node();

        // 建立左子树
        $node->left = $this->createBinaryTreePostOrder(array_shift($orders));

        // 建立右子树
        $node->right = $this->createBinaryTreePostOrder(array_shift($orders));

        // 建立根结点
        $data = array_shift($orders);
        if (is_null($data)) {
            return null; // null 表示子树为空
        }
        $node->data = $data;

        return $node;
    }

    /**
     * 先序遍历
     * @param $tree Node|null
     */
    public function preOrderTraversal($tree)
    {
        static $results = [];
        if (is_null($tree)) {
            return [];
        }
        // 访问根结点
        $results[] = $tree->data;
        // 访问左子树
        $this->preOrderTraversal($tree->left);
        // 访问右子树
        $this->preOrderTraversal($tree->right);
        return $results;
    }
    
    /**
     * 中序遍历
     * @param $tree Node|null
     */
    public function inOrderTraversal($tree)
    {
        static $results = [];
        if (is_null($tree)) {
            return [];
        }
        // 访问左子树
        $this->preOrderTraversal($tree->left);
        // 访问根结点
        $results[] = $tree->data;
        // 访问右子树
        $this->preOrderTraversal($tree->right);
        return $results;
    }

    /**
     * 后序遍历
     * @param $tree Node|null
     */
    public function postOrderTraversal($tree)
    {
        static $results = [];
        if (is_null($tree)) {
            return [];
        }

        // 访问左子树
        $this->preOrderTraversal($tree->left);
        // 访问右子树
        $this->preOrderTraversal($tree->right);
        // 访问根结点
        $results[] = $tree->data;
        return $results;
    }

    /**
     * 层次遍历（队列+循环）
     * 原理: 将同层级父节点统一出队的同时,将同一结层的所有子节点都入队
     * @param $tree Node|null
     * @return array
     */
    public function levelTraversal($tree)
    {
        $result = [];
        if (is_null($tree)) {
            return [];
        }

        $queue = new SplQueue();
        $queue->enqueue($tree);

        while (!$queue->isEmpty()) {
            /* @var $node Node */
            $node = $queue->dequeue();
            $result[] = $node->data;

            // 入队列的都是同一级的
            if (!is_null($node->left)) {
                $queue->enqueue($node->left);
            }
            if (!is_null($node->right)) {
                $queue->enqueue($node->right);
            }
        }

        return $result;
    }

    /**
     * 非递归的先序遍历
     * @param $tree Node|null
     * @return array
     */
    public function preOrderTraversalStack($tree)
    {
        if (is_null($tree)) {
            return [];
        }

        $stack = new SplStack();
        $result = [];

        /* @var $node Node */
        $node = $tree;
        while ($node || !$stack->isEmpty()) {
            if ($node) {
                $result[] = $node->data;
                $stack->push($node);
                $node = $node->left;
            } else {
                $node = $stack->pop();
                $node = $node->right;
            }
        }
        return $result;
    }

    /**
     * 非递归的先序遍历
     * @param $tree Node|null
     * @link https://www.processon.com/diagraming/5f4a2c676376890e62f89e87
     * @return array
     */
    public function preOrderTraversalStackV2($tree)
    {
        if (is_null($tree)) {
            return [];
        }

        $stack = new SplStack();
        $result = [];

        /* @var $node Node */
        $node = $tree;
        while ($node || !$stack->isEmpty()) {
            if ($node) {
                // 第一次从根结点访问,入栈,遍历左子树
                $result[] = $node->data;
                $stack->push([$node, false]);
                $node = $node->left;
            } else {
                [$node, $flag] = $stack->pop();
                if ($flag === false) {
                    // 第二次从左子树回来,回栈,遍历其右子树
                    $stack->push([$node, true]);
                    $node = $node->right;
                } else {
                    // 第三次从右子树回来,弹栈,消费掉
                    $node = null;
                }
            }
        }
        return $result;
    }

    /**
     * 非递归的中序遍历
     * @param $tree Node|null
     * @return array
     */
    public function inOrderTraversalStack($tree)
    {
        if (is_null($tree)) {
            return [];
        }

        $stack = new SplStack();
        $result = [];

        /* @var $node Node */
        $node = $tree;
        while ($node || !$stack->isEmpty()) {
            if ($node) {
                $stack->push($node);
                $node = $node->left;
            } else {
                $node = $stack->pop();
                $result[] = $node->data;
                $node = $node->right;
            }
        }
        return $result;
    }

    /**
     * 非递归的中序遍历V2
     * @param $tree Node|null
     * @return array
     */
    public function inOrderTraversalStackV2($tree)
    {
        if (is_null($tree)) {
            return [];
        }

        $stack = new SplStack();
        $result = [];

        /* @var $node Node */
        $node = $tree;
        while ($node || !$stack->isEmpty()) {
            if ($node) {
                // 第一次访问,先入栈,继续遍历其左子树
                $stack->push([$node, true]);
                $node = $node->left;
            } else {
                [$node, $flag] = $stack->pop();
                if ($flag === false) {
                    // 第二次访问,找到其右子树后回栈,遍历右子树
                    $result[] = $node->data;
                    $stack->push([$node, true]);
                    $node = $node->right;
                } else {
                    // 第三次访问,左右子树都已遍历完,弹出并消费掉此节点
                    $node = null;
                }
            }
        }
        return $result;
    }

    /**
     * 非递归的后序遍历
     * @param $tree Node|null
     * @return array
     */
    public function postOrderTraversalStack($tree)
    {
        if (is_null($tree)) {
            return [];
        }

        $stack = new SplStack();
        $result = [];

        /* @var $node Node */
        $node = $tree;
        while ($node || !$stack->isEmpty()) {
            if ($node) {
                // 第一次,从上层遍历到结点,先将node保存,并遍历其左子树
                $stack->push([$node, false]);
                $node = $node->left;
            } else {
                // 判断是从左子树遍历回来还是从右子树遍历回来
                [$node, $flag] = $stack->pop();
                if ($flag === false) {
                    // 第二次,从左子树遍历回来,node需要回栈
                    $stack->push([$node, true]);
                    $node = $node->right;
                } else {
                    // 第三次,从右子树遍历回来,弹出并消费掉
                    $result[] = $node->data;
                    $node = null;
                }
            }
        }
        return $result;
    }

    /**
     * 计算二叉树深度
     * @param $tree Node
     * @return int
     */
    public function depth($tree)
    {
        if (is_null($tree)) {
            return 0;
        }
        return max($this->depth($tree->left), $this->depth($tree->right)) + 1;
    }

    /**
     * 计算结点个数
     * @param $tree Node
     */
    public function length($tree)
    {
        if (is_null($tree)) {
            return 0;
        }
        return $this->length($tree->left) + $this->length($tree->right) + 1;
    }

    /**
     * 计算叶子结点个数
     * @param $tree Node
     * @return int
     */
    public function leafLength($tree)
    {
        if (is_null($tree)) {
            return 0;
        }
        if (is_null($tree->left) && is_null($tree->right)) {
            return 1;
        }
        return $this->leafLength($tree->left) + $this->leafLength($tree->right);
    }

    // todo 线索二叉树
}